package leetcode.hard.q30;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
//        new Solution().findSubstring();
        System.out.println(new Solution().findSubstring("mississippi", new String[]{"is"}));
//        System.out.println(new Solution().findSubstring("a", new String[]{"a"}));
//        System.out.println(new Solution().findSubstring("ababababab", new String[]{"ababa","babab"}));
    }
}

class Solution {
    HashMap<String,Integer> cnt = new HashMap<>();

    public List<Integer> findSubstring(String s, String[] words) {
        if (words.length==1&&s.length()==1) return s.equals(words[0])? Arrays.asList(0):new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        int len = words.length * words[0].length();
        if (len>s.length()) return new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            cnt.put(words[i],cnt.getOrDefault(words[i],0)+1);
        }
        for (int i = 0, k = i + len; k <=s.length(); i++,k=i+len) {
            String substring = s.substring(i, k);
            if (match(substring, words[0].length(), cnt)) {
                res.add(i);
            }

        }

        return res;
    }

    private boolean match(String substring, int wordLen, HashMap<String,Integer> stringSet) {
        HashMap<String,Integer> count = new HashMap<>(stringSet);

        for (int i = 0; i < substring.length(); i += wordLen) {
            String substring1 = substring.substring(i, i + wordLen);
            if (count.containsKey(substring1)) {
                int i1 = count.get(substring1) - 1;
                if (i1 == 0) count.remove(substring1);
                else count.put(substring1,i1);
            }else return false;
        }
        return count.size()==0;
    }


}

class Solution1 {
    Set<String> stringSet = new HashSet<>();

    public List<Integer> findSubstring(String s, String[] words) {
        for (int i = 0; i < words.length; i++) {
            append(i, words);
        }
        System.out.println(stringSet);
        return null;
    }

    //1 2 3
    //123 213
    void append(int i, String[] words) {
        System.out.println(">第：" + i);
        stringSet.add(toStr(words));
        for (int j = i; j < words.length; j++) {
            swap(i, j, words);//213
            append(j, words);
            toStr(words);
            swap(i, j, words);
            toStr(words);

        }
        System.out.println("<第：" + i);
        toStr(words);
    }

    private String toStr(String[] words) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            stringBuilder.append(words[i]);

        }
        System.out.println(stringBuilder);
        return stringBuilder.toString();
    }

    void swap(int a, int b, String[] words) {
        String t = words[a];
        words[a] = words[b];
        words[b] = t;
    }
}